20.4 Quadratic Probing

What's Quadratic Probing?

	scan cells 1, 4, 9 away from the original probe
	eliminates primary clustering
	if the hash function gives H, scan H+(i^2) instead of H+i

Show the result of inserting 2, 7, 3, 8 into a hash table of size 5.


Classwork
You may work with a partner.
Show the result of inserting 7, 6, 1, 2 into a hash table of size 5.


Does quadratic probing try all cells?

	if the table size is prime
	and the load factor is <= 0.5
	probes will be to different locations


Linear Probing is fast and easy (increment, wraparound).
Quadratic Probing appears expensive (increment, square, add, wraparound).
Can you implement quadratic probing efficiently?

	increment i          (i+1)
	shift left 1 bit     (2(i+1))
	subtract 1           (2(i+1) - 1)
	add to old position
	test for wrap-around

How does adding 2(i+1)-1 to the old position give the same result as H + (i+1)^2?

	(H + (i+1)^2) - (H + (i)^2) = 2i + 1 = 2(i+1) - 1


What should you do when the load factor exceeds 0.5?

	Rehashing
	make a new table twice as big (but use a prime number)
	find the next prime number at least twice as large

Do you copy each item from the old table to the same location in the new table?

	no, the hash function is different because the table size is different
	hash each item into the new table


How well does Quadratic Probing perform?

	eliminates primary clustering
	suffers from secondary clustering

What's Secondary Clustering?

	elements that hash to the same position probe the same alternate cells
	causes less than an extra half-probe per search

Can you eliminate Secondary Clustering?

	yes, use Double Hashing
	use a second hash function for collision resolution
	H(x) + 0*H2(x)
	H(x) + 1*H2(x)
	H(x) + 2*H2(x)
	H(x) + i*H2(x)